// 5-29 6.40 暂时没弄懂 mark*
// 6.39 假设在二叉链表的结点中增设两个域：双亲域（parent）以指示其双亲结点；标志域（mark取值0、1、2）以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法
// 6.40 若在二叉链表的结点中只增设一个双亲域以指示其双亲结点，则在遍历过程中能否不设栈？试以此存储结构编写不设栈进行中序遍历的递推形式的算法。

#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
    int data, tag;
    struct tree *left, *right, *parent;
};

void create_tree(tree *&root, int array[], int n, int index)
{
    if (index > n)
        return;
    if (array[index] == NULL)
    {
        root = NULL;
        return;
    }
    root = (tree *)malloc(sizeof(tree));
    root->data = array[index];
    root->tag = 0;
    root->left = root->right = root->parent = NULL;
    create_tree(root->left, array, n, 2 * index + 1);
    create_tree(root->right, array, n, 2 * index + 2);
    if (root->left)
        root->left->parent = root;
    if (root->right)
        root->right->parent = root;
    return;
}

void fun_6_39(tree *root)
{
    while (root)
    {
        switch (root->tag)
        {
        case 0:
            root->tag++;
            if (root->left)
                root = root->left;
            break;
        case 1:
            root->tag++;
            if (root->right)
                root = root->right;
            break;
        case 2:
            root->tag = 0;
            printf("%3d", root->data);
            root = root->parent;
            break;
        default:
            break;
        }
    }
}
void fun_6_40(tree *root)
{
    while (root)
    {
        if (root->left)
        {
            root = root->left; //第一次访问 进左子树
        }
        else
        {
            printf("%3d", root->data); //第二次访问 输出
            while (!(root->right))
            {
                while (root->parent && root == root->parent->right)
                    root = root->parent; //退回到不是右子树的位置
                if (root->parent)        //不为根节点
                {
                    if (root = root->parent->left)
                    {
                        root = root->parent;
                        printf("%3d", root->data);
                    }
                }
                else //当前节点为根节点
                    return;
            }
            root = root->right;
        }
    }
}
int main()
{
    /*******************code*******************/
    int n = 15;
    int a[15] = {1,
                 2, 8,
                 5, 3, NULL, 9,
                 NULL, 6, 7, 4, NULL, NULL, NULL, NULL};
    tree *root;
    create_tree(root, a, n, 0);
    fun_6_39(root);
    printf("\n\n****************************\n");
    fun_6_40(root);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
